package _27_字符串的排列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

/*
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 */
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if (str.length() == 0) return res;
        char c[] = str.toCharArray();
        digui(c, res, 0);
        return res;
    }

    void digui(char c[], ArrayList<String> res, int begin) {
        if (begin == c.length - 1) {
            String s = new String(c);

            //对于重复字符，比如aa，全排列后有两个aa，所以要去重
            if (!res.contains(s)) {
                res.add(s);
            }
        } else {
            for (int i = begin; i < c.length; i++) {
                //当序号不同但是字母相同时候，不需要交换
                if ((i != begin) && (c[i] == c[begin])) continue;
                swap(c, begin, i);
                digui(c, res, begin + 1);
                //回溯
                swap(c, begin, i);
            }
        }
    }


    void swap(char[] c, int i, int j) {
        char tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        System.out.println(solution.Permutation("abc"));
    }
}
//子集
class Solution2 {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if (str.length() == 0) return res;
        char c[] = str.toCharArray();
        digui(c, res, new StringBuilder(), 0);
        return res;
    }

    void digui(char c[], ArrayList<String> res, StringBuilder sb, int begin) {
        if(begin==c.length) return;
         sb.append(c[begin]);
         res.add(sb.toString());
         digui(c,res,sb,begin+1);
         //回溯到之前
         sb.deleteCharAt(sb.length()-1);
         //添加下一个元素，
         digui(c,res,sb,begin+1);
    }


}

